#ifndef __SIMPLE_PATH_H__
#define __SIMPLE_PATH_H__

#include "dynamic-tree.h"
#include "path.h"
#include "tree-algorithms.h"

namespace Trees
{
	template <class V, class E> class SimplePath;
	
	template <class V, class E>
	class SimplePathTree : public DynamicPathTree<V,E>
	{
	public:
		SimplePathTree(const V& value, DotPrinter* forest);
		virtual ~SimplePathTree();

		const E MinEdge() const;
		const E MaxEdge() const;
		
		Path<V,E>* GetPath() const;
		DynamicPathTree<V,E>* Before() const;
		DynamicPathTree<V,E>* After() const;
		const E PCost() const;
		Path<V,E>* Expose(const string& logPrefix = "") const;
		void Split(Trees::Path<V,E>** p, Trees::Path<V,E>** q, E* x, E* y, const string& logPrefix = "");
		
		virtual void Link(DynamicTree<V,E>* otherRoot, const E& x);
	
	private:
		E m_cost;
		SimplePathTree<V,E>* m_after;
		SimplePathTree<V,E>* m_before;
		
		// Only head of path keep the reference to Path, other elements may have invalid references
		SimplePath<V,E>* m_path;
		
		DotPrinter* m_forest;
		
		template <class V1, class E1> friend class SimplePath;
		template <class E1> friend class PathForest;
	};
	
	
	/*********************************************************************
	 *
	 *                   S I M P L E    P A T H 
	 *
	 ********************************************************************/
	template <class V, class E>
	class SimplePath : public Path<V,E>
	{
	public:
		SimplePath(SimplePathTree<V,E>* head);
		SimplePath(SimplePathTree<V,E>* head, SimplePathTree<V,E>* tail);
		virtual ~SimplePath();
		
		DynamicPathTree<V,E>* Head() const;
		DynamicPathTree<V,E>* Tail() const;
		DynamicPathTree<V,E>* PMinCost() const;
		void PUpdate(const E& x);
		void Reverse();
		Path<V,E>* Concatenate(Path<V,E>* tail, const E& x);
		Path<V,E>* Splice();
		
	private:
		SimplePathTree<V,E>* m_head;
		SimplePathTree<V,E>* m_tail;
		V m_id;
		
		template <class V1, class E1> friend class SimplePathTree;
		template <class E1> friend class PathForest;
	};
	
	/*********************************************************************
	 *
	 *             T R E E    A L L O C A T O R
	 *
	 ********************************************************************/
	template <class V, class E>
	class SimplePathTreeAllocator : public TreeAllocator<V,E>
	{
	public:
		DynamicTree<V,E>* CreateTree(const V& value) const
		{
			return new SimplePathTree<V,E>(value);
		}
	};
	
}

#endif
